001.Two Sum[E]

1.题目

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

  1. Given nums = [2, 7, 11, 15], target = 9,
  2. Because nums[0] + nums[1] = 2 + 7 = 9,
  3. return [0, 1].

2.思路

作为我们可能进入leetcode遇到的第一题，大家对它可谓是又爱又恨，而且它确实又有很多解法，总结起来可以有以下3种，3种还都能A过….

2.1双重循环

最简单的思路，两重循环，没啥技术含量，速度很慢，毕竟是$O(N^2)$

  1. class Solution {
  2. public:
  3.     vector<int> twoSum(vector<int>& nums, int target) {
  4.         vector<int> result;
  5.         for(int i = 0;i < nums.size();i++)
  6.         {
  7.             for(int j = i+1;j < nums.size();j++)
  8.                 if(nums[i] + nums[j] == target)
  9.                 {
  10.                     result.push_back(i);
  11.                     result.push_back(j);
  12.                     return result;
  13.                 }
  15.         }
  16.     }
  17. };

2.2 排序

其实简单的想，用一个排序都能把复杂度降到$O(NlogN)$，通过排序，然后用两个指针从前后扫描逼近真值(注意这个思想，可以让O(N*N)的复杂度降为O(N),充分利用排序，因为一定会有一个值满足，然后通过值去原数组里找对应的下标（这里其实就可以考虑，如果当初就用一个数据结构存好键值对应关系就好了，其实就是hashmap，下面的做法就用到了）
（下面代码是 dugu9sword写的java代码，我就没写成c++的，主要看思路，还是比较好理解的）

  1. public class Solution {
  2.     public int[] twoSum(int[] nums, int target) {
  3.         int[] nums_sorted=new int[nums.length];
  4.         System.arraycopy(nums,0,nums_sorted,0,nums.length);
  5.         //Quicksort.
  6.         Arrays.sort(nums_sorted);
  8.         //Find the two numbers. O(n)
  9.         int start=0;
  10.         int end=nums_sorted.length;
  11.         while(start<end){
  12.             while(nums_sorted[start]+nums_sorted[--end]>target);
  13.             if(nums_sorted[end]+nums_sorted[start]==target)
  14.                 break;
  15.             while(nums_sorted[++start]+nums_sorted[end]<target);
  16.             if(nums_sorted[end]+nums_sorted[start]==target)
  17.                 break;
  18.         }
  20.         //find the indices of the two numbers
  21.         int[] ret=new int[2];
  22.         int index=0;
  23.         int a=nums_sorted[start];
  24.         int b=nums_sorted[end];
  25.         for(int i=0;i<nums.length;i++)
  26.             if(nums[i]==a || nums[i]==b)
  27.                 ret[index++]=i;
  28.         return ret;
  29.     }
  30. }

2.3 Hashmap

最后一种是比较聪明的做法，用hashmap，hashmap是内部存储方式为哈希表的map结构，哈希表可以达到查找O(1)，哈希表的介绍可以看这里, C++实现Hashmap的方式，这里用unordered_map关联容器，可以实现键值对应。

  1. class Solution {
  2. public:
  3.     vector<int> twoSum(vector<int>& nums, int target) {
  4.         vector<int> result;
  5.         unordered_map<int,int> mymap;
  6.         int res;
  7.         for(int i = 0;i < nums.size();i++)
  8.         {
  9.             res = target - nums[i];
  10.             unordered_map<int,int>::iterator it = mymap.find(res);
  11.             if(it != mymap.end())
  12.             {
  13.                 return vector<int>({it->second,i});
  14.             }
  15.             mymap[nums[i]] = i;
  16.         }
  17.     }
  18. };